By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

ALERT ATTENTION: System maintenance will be performed the weekend of Saturday, March 28, 2009. This event will begin at 6:00 am on March 28 and will conclude at approximately 12:00 noon on Sunday March 29 (all times EDT). Some Scitation services may be affected during this period.
Table of Contents
Search This Issue
Volume 31, Issue 1, pp. 1-330

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling

Jianer Chen and Antonio Miranda

pp. 1-17

BibTeX  Abstract Full Text:  PDF

A Decomposition Theorem for Maximum Weight Bipartite Matchings

Ming-Yang Kao, Tak-Wah Lam, Wing-Kin Sung, and Hing-Fung Ting

pp. 18-26

BibTeX  Abstract Full Text:  PDF

Traveling Salesman-Based Curve Reconstruction in Polynomial Time

Ernst Althaus and Kurt Mehlhorn

pp. 27-66

BibTeX  Abstract Full Text:  PDF

Tree Search on an Atomic Model for Message Passing

Pangfeng Liu, William Aiello, and Sandeep Bhatt

pp. 67-85

BibTeX  Abstract Full Text:  PDF

On-line Randomized Call Control Revisited

Stefano Leonardi, Alberto Marchetti-Spaccamela, Alessio Presciutti, and Adi Rosén

pp. 86-112

BibTeX  Abstract Full Text:  PDF

Fixed-Parameter Tractability, Definability, and Model-Checking

Jörg Flum and Martin Grohe

pp. 113-145

BibTeX  Abstract Full Text:  PDF

Approximation Techniques for Average Completion Time Scheduling

C. Chekuri, R. Motwani, B. Natarajan, and C. Stein

pp. 146-166

BibTeX  Abstract Full Text:  PDF

Markov Chain Algorithms for Planar Lattice Structures

Michael Luby, Dana Randall, and Alistair Sinclair

pp. 167-192

BibTeX  Abstract Full Text:  PDF

There are No Sparse NPw-Hard Sets

Felipe Cucker and Dima Grigoriev

pp. 193-198

BibTeX  Abstract Full Text:  PDF

Randomness and Recursive Enumerability

Antonín Kucera and T. Slaman

pp. 199-211

BibTeX  Abstract Full Text:  PDF

Treewidth and Minimum Fill-in: Grouping the Minimal Separators

Vincent Bouchitté and Ioan Todinca

pp. 212-232

BibTeX  Abstract Full Text:  PDF

The Accommodating Function: A Generalization of the Competitive Ratio

Joan Boyar, Kim S. Larsen, and Morten N. Nielsen

pp. 233-258

BibTeX  Abstract Full Text:  PDF

Generating Bracelets in Constant Amortized Time

Joe Sawada

pp. 259-268

BibTeX  Abstract Full Text:  PDF

Disjunctions of Horn Theories and Their Cores

Thomas Eiter, Toshihide Ibaraki, and Kazuhisa Makino

pp. 269-288

BibTeX  Abstract Full Text:  PDF

A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs

Pavol Hell, Ron Shamir, and Roded Sharan

pp. 289-305

BibTeX  Abstract Full Text:  PDF

Provably Fast and Accurate Recovery of Evolutionary Trees through Harmonic Greedy Triplets

Miklós Csurös and Ming-Yang Kao

pp. 306-322

BibTeX  Abstract Full Text:  PDF

Proportion Extend Sort

Jing-Chao Chen

pp. 323-330

BibTeX  Abstract Full Text:  PDF